/*

step 1
populate int array w/ 1000 unique ints, 0-9999

step 2
randomly generate index 0-999 (since array has 1000 elements)
use as index for array
return value at index

step 3
linear search - locate key
keep track of # of comparisons needed to find key
return # of comparisons

step 4
sort array in ascending order

step 5
binary search - locate key
keep track of # of comparisons needed to find key
return # of comparisons

step 6
write main function
loop: loops 1000 times
call each function
accumulate data

*/

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

/* function prototypes */

int generateNumberInRange(int min, int max);
void printNumbers(int numbers[], int size, char sep);

void populateArray(int arrayOut[], int size);
int getRandomValue(int arrayIn[], int size);
void sortArray(int arrayIO[], int size);
int doLinearSearch(int arrayIn[], int size, int key);
int doBinarySearch(int arrayIn[], int size, int key);

/* main function */

void main()
{
	srand(time(NULL));

	const int SIZE = 1000;
	int theArray[SIZE] = {0};
	populateArray(theArray, SIZE);

	int randomValue = getRandomValue(theArray, SIZE);
	cerr << "Random value: " << randomValue << endl;

	int triesLinear = doLinearSearch(theArray, SIZE, randomValue);
	cerr << "LINEAR: took " << triesLinear << " comparisons to find the value.\n";

	sortArray(theArray, SIZE);

	int triesBinary = doBinarySearch(theArray, SIZE, randomValue);
	cerr << "BINARY: took " << triesBinary << " comparisons to find the value.\n";
}

/* function definitions */

int generateNumberInRange(int min, int max)
{
	return rand() % (max - min + 1) + min;
}

void printNumbers(int numbers[], int size, char sep)
{
	for (int i = 0; i < size; i++)
		cout << numbers[i] << sep;
}

void populateArray(int arrayOut[], int size)
{
	for (int i = 0; i < size; i++)
	{
		int randomNumber = generateNumberInRange(0, 9999);
		arrayOut[i] = randomNumber;
	}
}

int getRandomValue(int arrayIn[], int size)
{
	int randomIndex = generateNumberInRange(0, size - 1);
	return arrayIn[randomIndex];
}

void sortArray(int arrayIO[], int size)
{
	bool swapped;

	do {
		swapped = false;
		for (int i = 0; i < size - 1; i++)
		{
			int current = arrayIO[i];
			int next = arrayIO[i + 1];

			if (current > next)
			{
				arrayIO[i] = next;
				arrayIO[i + 1] = current;
				swapped = true;
			}
		}
	} while (swapped);
}

int doLinearSearch(int arrayIn[], int size, int key)
{
	int comparisons = 0;

	for (int i = 0; i < size; i++)
	{
		comparisons++;
		if (arrayIn[i] == key)
			break;
	}

	return comparisons;
}

int doBinarySearch(int arrayIn[], int size, int key)
{
	int comparisons = 0;
	int imin = 0, imax = size - 1;

	int val;
	bool done = false;
	do {
		comparisons++;

		int imid = (imin + imax) / 2;
		val = arrayIn[imid];

		if (val > key)
			imax = imid - 1;
		else if (val < key)
			imin = imid + 1;
	} while (val != key);

	return comparisons;
}

